package com.cn.algorithm02.class10;

import java.util.Stack;

/***
 * @author: hels
 * @description: 二叉树前序，中序，后序遍历
 *   a
 *  b c
 * de fg
    前：A B D E C F G
    中：D B E A F C G
    后：D E B F G C A
 **/
public class C01_BinaryTreeOrder {
    public static void main(String[] args) {
        Node d = new Node("D", null, null);
        Node e = new Node("E", null, null);
        Node f = new Node("F", null, null);
        Node g = new Node("G", null, null);
        Node b = new Node("B", d, e);
        Node c = new Node("C", f, g);
        Node a = new Node("A", b, c);
        suf(a);
        System.out.println();
        sufOrder(a);

    }

    // 1 递归处理
    // 前序
    public static void pre(Node head) {
        if (head == null) return;

        System.out.print(head.value + " ");
        pre(head.left);
        pre(head.right);
    }
    // 中序
    public static void in(Node head) {
        if (head == null) return;

        in(head.left);
        System.out.print(head.value + " ");
        in(head.right);
    }
    // 后序
    public static void suf(Node head) {
        if (head == null) return;

        suf(head.left);
        suf(head.right);
        System.out.print(head.value + " ");
    }

    // 2 非递归方式处理， 前中后
    // 前序
    public static void preOrder(Node node) {
        if (node == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (stack.size() > 0) {
            Node cur = stack.pop();
            System.out.print(cur.value + " ");
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }


    }
    // 中序
    public static void inOrder(Node node) {
        if (node == null) return;

        Stack<Node> stack = new Stack<>();
        // stack.push(node);
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                System.out.print(node.value + " ");
                node = node.right;
            }
        }
    }

    // 后序
    public static void sufOrder(Node node ) {
        if (node == null) return;
        Stack<Node> stack = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            node = stack.pop();
            //System.out.print(node.value + " ");
            stack2.push(node);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value + " ");
        }
    }

}
